import common.ListNode;

/**
 * 61. Rotate List 旋转链表
 * https://leetcode-cn.com/problems/rotate-list/
 */
class RotateList {
    /**
     * 方法：将链表向右旋转k个位置。先计算链表长度，然后将尾节点与头节点相连形成环，最后在正确位置断开环形成新的链表。
     * 
     * Args:
     *   head: 链表头节点
     *   k: 向右旋转的位置数
     * 
     * Returns:
     *   旋转后的链表头节点
     * 
     * Time: O(n)，其中n为链表长度
     * 
     * Space: O(1)，只使用常数额外空间
     */
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0){
            return head;
        }
        // 计算链表长度并记录尾节点
        int n = 1;
        ListNode tail = head;
        while(tail.next != null){
            tail = tail.next;
            n++;
        }
        k = k % n;
        if(k == 0){
            return head; 
        }
        // 形成环形链表
        tail.next = head;
        // 找到新头节点和新尾节点
        ListNode newTail = head;
        for(int i = 0; i< n - k - 1; i++){
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}